package  com.ywgt.avl;

public class AVLTree {

    public static void main(String[] args) {
        int [] arr={1,-5,3,5,-1,14,11,13,15};
        BinarySortNode binarySortNode=new BinarySortNode();
        for (int i = 0; i < arr.length; i++) {
            binarySortNode.add(new BinaryNode(arr[i]));
        }
        binarySortNode.infixOrder();
        binarySortNode.binaryNode.leftHeight();
        System.out.println(binarySortNode.binaryNode.leftHeight());
        System.out.println(binarySortNode.binaryNode.rightHeight());
    }
}


class BinarySortNode{
    BinaryNode binaryNode;

    public void add(BinaryNode node){
        if(binaryNode==null){
            binaryNode=node;
        }else {
            binaryNode.add(node);
        }
    }


    public void delete(int val){
        if(binaryNode==null){
            System.out.println("空树");
            return;
        }
        //如果只有一个节点，并且val相等，直接置为空
        if(binaryNode.left==null&&binaryNode.right==null&&binaryNode.val==val){
            binaryNode=null;
            return;
        }
        //查询待删除的目标节点
        BinaryNode target = search(val);
        //查询待删除节点的父节点
        BinaryNode parent = searchParent(val);
        //如果没有直接返回
        if(target==null){
            return;
        }
        //如果parent为null那么证明要删除当前的树的顶节点
        if(parent==null){
            //向右查找最小元素，进行赋值
            int i = searchRightMin(this.binaryNode);
            this.binaryNode.val=i;
            return;
        }
        //如果待删除节点的左右节点都为空，则为叶子节点，直接更改父节点的指针为null
        if(target.left==null&&target.right==null){
            if(parent.left==target){
                parent.left=null;
            }
            if(parent.right==target){
                parent.right=null;
            }
        }else if(target.left!=null&&target.right!=null){//当左右节点都不为空，证明有两个子节点，则需要进行向右节点查询最小数，置换
            int i = searchRightMin(target);
            target.val=i;
        }else {
            //当前待删除节点只有一个子节点
            if(target.left!=null&&parent.left==target){
                parent.left=target.left;
            }
            if(target.right!=null&&parent.left==target){
                parent.left=target.right;
            }
            if(target.left!=null&&parent.right==target){
                parent.right=target.left;
            }
            if(target.right!=null&&parent.right==target){
                parent.right=target.right;
            }
        }
    }

    /**
     * 若删除有两个子节点的元素，那么需要查询右子节点中最小或者左子节点最大的元素
     * @param node
     * @return
     */
    public int searchRightMin(BinaryNode node){
        BinaryNode temp=node;
        if(node==this.binaryNode){ //如果是当前的头结点那么，让temp=节点的右节点下找寻最小的
            temp=temp.right;
        }
        while(temp.left!=null){
            temp=temp.left;
        }
        delete(temp.val);  //删除到找到那个节点，因为将这个值要附到删除的节点位置上
        return temp.val;
    }

    public void infixOrder(){
        if(this.binaryNode==null){
            System.out.println("空树");
            return;
        }
        this.binaryNode.infixOrder();
    }

    public BinaryNode search(int val){
        if(this.binaryNode==null){
            return null;
        }
        return binaryNode.searchTarget(val);
    }
    public BinaryNode searchParent(int val){
        if(this.binaryNode==null){
            return null;
        }
        return binaryNode.serchParent(val);
    }

}

class  BinaryNode{
     int val;
     BinaryNode left;
     BinaryNode right;

    public BinaryNode(int val) {
        this.val = val;
    }

    @Override
    public String toString() {
        return "BinaryNode{" +
                "val=" + val +
                '}';
    }

    /**
     * 左节点高度
     */
    public int leftHeight(){
        if(left==null){
            return 0;
        }
        return left.height();
    }

    /**
     * 右节点高度
     */
    public int rightHeight(){
        if(right==null){
            return 0;
        }
        return right.height();
    }
    /**
     * 获得节点的高度
     */
    public int height(){
        return Math.max(left==null? 0:left.height(),right==null? 0: right.height())+1;
    }

    /**
     * 查找父元素
     */
    public BinaryNode serchParent(int val){
        if(this.left!=null&&this.left.val==val||this.right!=null&&this.right.val==val){//找到的条件
            return this;
        }
        else if(this.left!=null&&this.val>val){ //若是比当前节点val小，那么向左递归查找
            return this.left.serchParent(val);
        }else if(this.right!=null&&this.val<val){//若是比当前节点val大，那么向右递归查找
            return this.right.serchParent(val);
        }
        return null;
    }
    /**
     * 查找target元素
     */
    public BinaryNode searchTarget(int val){
        if(val==this.val){//查询条件
            return this;
        }
        else if(val<this.val&&this.left!=null){//若是比当前节点val小，那么向左递归查找
            return this.left.searchTarget(val);
        }else if(val>this.val&&this.right!=null){//若是比当前节点val大，那么向右递归查找
            return this.right.searchTarget(val);
        }
        return null;
    }

    /**
     * 添加元素
     * @param binaryNode
     */
    public void add( BinaryNode binaryNode){
        if(this.val>binaryNode.val) {
            if (this.left == null) {
                this.left = binaryNode;
            } else {
                this.left.add(binaryNode);
            }
        } else  {
            if (this.right == null) {
                this.right = binaryNode;
            } else {
                this.right.add(binaryNode);
            }
        }

        /**
         * 以下为自旋转代码，平衡二叉树
         */
        //当右子树高比左子树高度大于1时左旋转
        if(rightHeight()-leftHeight()>1){
            if(right!=null&&right.leftHeight()>right.rightHeight()){
                right.rightRotate();
            }
            leftRotate();
            return;
        }
        if(leftHeight()-rightHeight()>1){
            //如果左子树的右子树高度大于左子树高度，以子节点进行左旋转
            if(left!=null&&left.rightHeight()>left.leftHeight()){
                left.leftHeight();
            }
            rightRotate();
        }

    }

    /**
     * 左旋转 当右子树高度比左子树高度大于1时
     */
    public void leftRotate(){
        BinaryNode newNode = new BinaryNode(val);
        newNode.left=left;
        newNode.right=right.left;
        val=right.val;
        right=right.right;
        left=newNode;
    }


    public void rightRotate(){
        BinaryNode newNode = new BinaryNode(val);
        newNode.right=right;
        newNode.left=left.right;
        val=left.val;
        left=left.left;
        right=newNode;
    }

    /**
     * 中序遍历
     */
    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }
}
